//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// lru_k_replacer.cpp
//
// Identification: src/buffer/lru_k_replacer.cpp
//
// Copyright (c) 2015-2022, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include "buffer/lru_k_replacer.h"
#include "common/exception.h"
#include "common/logger.h"

namespace bustub {

LRUKReplacer::LRUKReplacer(size_t num_frames, size_t k) : replacer_size_(num_frames), k_(k) {
  head_ = new LRUKNode();
  mid_ = new LRUKNode();
  tail_ = new LRUKNode();

  head_->next_ = mid_;
  mid_->prev_ = head_;
  mid_->next_ = tail_;
  tail_->prev_ = mid_;
  // LOG_DEBUG("replacer_size_=%ld, k_=%ld", replacer_size_, k_);
}

LRUKReplacer::~LRUKReplacer() {
  LRUKNode *node;
  std::vector<LRUKNode *> node_vec;
  for (node = head_; node != tail_; node = node->next_) {
    node_vec.push_back(node);
  }
  node_vec.push_back(tail_);
  for (auto node : node_vec) {
    delete node;
  }
}

auto LRUKReplacer::Evict(frame_id_t *frame_id) -> bool {
  std::unique_lock<std::mutex> lk(latch_);
  bool found = false;

  // evict history->mid_
  auto cur = mid_->prev_;
  while (cur != head_ && !found) {
    if (cur->evictable_) {
      *frame_id = cur->key_;
      curr_size_--;
      node_size_--;
      node_store_.erase(*frame_id);
      RemoveNode(cur);
      delete cur;
      found = true;
      break;
    }
    cur = cur->prev_;
  }
  // evict history->tail_
  cur = tail_->prev_;
  while (cur != mid_ && !found) {
    if (cur->evictable_) {
      *frame_id = cur->key_;
      curr_size_--;
      node_size_--;
      node_store_.erase(*frame_id);
      RemoveNode(cur);
      delete cur;
      found = true;
      break;
    }
    cur = cur->prev_;
  }
  // LOG_DEBUG("found=%d, frame_id=%d", found, *frame_id);
  return found;
}

void LRUKReplacer::RecordAccess(frame_id_t frame_id, [[maybe_unused]] AccessType access_type) {
  std::unique_lock<std::mutex> lk(latch_);
  // LOG_DEBUG("frame_id=%d", frame_id);
  BUSTUB_ASSERT(frame_id >= 0 && (size_t)frame_id < replacer_size_, "invalid frame");
  auto it = node_store_.find(frame_id);

  // first access
  if (it == node_store_.end()) {
    if (replacer_size_ == node_size_) {
      return;
    }
    auto *node = new LRUKNode(frame_id, 1, false);
    node_store_[frame_id] = node;
    AddToNext(node, head_);
    node_size_++;
    return;
  }
  auto *node = it->second;
  if (++node->k_ >= k_) {
    MoveToMid(node);
  }
}

void LRUKReplacer::SetEvictable(frame_id_t frame_id, bool set_evictable) {
  std::unique_lock<std::mutex> lk(latch_);
  // LOG_DEBUG("frame_id=%d, set_evictable=%d", frame_id, set_evictable);
  auto it = node_store_.find(frame_id);
  if (it == node_store_.end()) {
    return;
  }
  if (it->second->evictable_ == set_evictable) {
    return;
  }
  it->second->evictable_ = set_evictable;
  if (set_evictable) {
    curr_size_++;
    return;
  }
  curr_size_--;
}

void LRUKReplacer::Remove(frame_id_t frame_id) {
  std::unique_lock<std::mutex> lk(latch_);
  // LOG_DEBUG("frame_id=%d", frame_id);
  auto it = node_store_.find(frame_id);
  if (it == node_store_.end()) {
    return;
  }
  auto node = it->second;
  if (!node->evictable_) {
    throw ExecutionException("non-evictable frame");
  }
  curr_size_--;
  node_size_--;
  node_store_.erase(frame_id);
  RemoveNode(node);
  delete node;
}

auto LRUKReplacer::Size() -> size_t {
  std::unique_lock<std::mutex> lk(latch_);
  // LOG_DEBUG("curr_size_=%ld", curr_size_);
  return curr_size_;
}

}  // namespace bustub
